use std::cell::{Ref, RefMut};
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};
use std::ops::DerefMut;
use std::{
    cell::RefCell,
    collections::{HashMap, HashSet, VecDeque},
    fmt::Display,
    ops::Deref,
    rc::Rc,
};

struct Node<T: Display + Ord + PartialOrd> {
    no: T,
    elem: i32,
    in_dgree: usize,
    out_dgree: usize,
    next: Vec<NodeLink<T>>,
    edges: Vec<EdgeLink<T>>,
}
impl<T: Display + Ord + PartialOrd> Node<T> {
    fn new(no: T) -> Self {
        Self {
            no,
            elem: 0,
            in_dgree: 0,
            out_dgree: 0,
            next: Vec::new(),
            edges: Vec::new(),
        }
    }
}
impl<T: Display + Ord + PartialOrd> Display for Node<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(
            f,
            "No: {}, elem:{}, in: {}, out:{}",
            self.no, self.elem, self.in_dgree, self.out_dgree
        )?;

        if !self.next.is_empty() {
            write!(f, "next: [{}]", self.next[0].inner().no)?;
            for n in &self.next[1..] {
                write!(f, ", [{}]", n.inner().no)?;
            }
            writeln!(f, "")?;
        } else {
            writeln!(f, "next: None")?;
        }

        if !self.edges.is_empty() {
            write!(f, "edges: {}", self.edges[0])?;
            for e in &self.edges[1..] {
                write!(f, ", {}", e)?;
            }
            writeln!(f, "")?;
        } else {
            writeln!(f, "edges: None")?;
        }

        Ok(())
    }
}

struct NodeLink<T: Display + Ord + PartialOrd>(Option<Rc<RefCell<Node<T>>>>);
impl<T: Display + Ord + PartialOrd> Display for NodeLink<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_none() {
            write!(f, "None")?;
            return Ok(());
        }
        write!(f, "{}", self.inner())?;

        Ok(())
    }
}
impl<T: Display + Ord + PartialOrd> Deref for NodeLink<T> {
    type Target = Option<Rc<RefCell<Node<T>>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T: Display + Ord + PartialOrd> Clone for NodeLink<T> {
    fn clone(&self) -> Self {
        NodeLink(self.as_ref().map(|nd| nd.clone()))
    }
}
impl<T: Display + Ord + PartialOrd> Eq for NodeLink<T> {}
impl<T: Display + Ord + PartialOrd> PartialEq for NodeLink<T> {
    fn eq(&self, other: &Self) -> bool {
        let lp = self.as_ref().map(|node| node.as_ptr());
        let rp = other.as_ref().map(|node| node.as_ptr());
        lp == rp
    }
}
impl<T: Display + Ord + PartialOrd> Hash for NodeLink<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        if self.is_none() {
            0.hash(state);
        } else {
            self.as_ref().map(|node| node.as_ptr().hash(state));
        }
    }
}

impl<T: Display + Ord + PartialOrd> NodeLink<T> {
    fn new(no: T) -> Self {
        NodeLink(Some(Rc::new(RefCell::new(Node::new(no)))))
    }

    fn inner(&self) -> Ref<Node<T>> {
        self.as_ref().unwrap().borrow()
    }
    fn inner_mut(&self) -> RefMut<Node<T>> {
        self.as_ref().unwrap().borrow_mut()
    }
}

struct Edge<T: Display + Ord + PartialOrd> {
    weight: i32,
    from: T,
    to: T,
}
impl<T: Display + Ord + PartialOrd> Edge<T> {
    fn new(weight: i32, from: T, to: T) -> Self {
        Self { weight, from, to }
    }
}
impl<T: Display + Ord + PartialOrd> Display for Edge<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "([{}] --{}--> [{}])", self.from, self.weight, self.to)?;
        Ok(())
    }
}
struct EdgeLink<T: Display + Ord + PartialOrd>(Option<Rc<RefCell<Edge<T>>>>);
impl<T: Display + Ord + PartialOrd> Display for EdgeLink<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_none() {
            write!(f, "None")?;
            return Ok(());
        }

        write!(f, "{}", self.inner())?;

        Ok(())
    }
}
impl<T: Display + Ord> Hash for EdgeLink<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        if self.is_none() {
            0.hash(state);
        } else {
            self.as_ref().map(|node| node.as_ptr().hash(state));
        }
    }
}

impl<T: Display + Ord> Eq for EdgeLink<T> {}
impl<T: Display + Ord> PartialEq for EdgeLink<T> {
    fn eq(&self, other: &Self) -> bool {
        self.inner().weight == other.inner().weight
    }
}
impl<T: Display + Ord> Ord for EdgeLink<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.inner().weight.cmp(&other.inner().weight)
    }
}
impl<T: Display + Ord> PartialOrd for EdgeLink<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.inner().weight.cmp(&other.inner().weight))
    }
}
impl<T: Display + Ord> Deref for EdgeLink<T> {
    type Target = Option<Rc<RefCell<Edge<T>>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T: Display + Ord + PartialOrd> Clone for EdgeLink<T> {
    fn clone(&self) -> Self {
        EdgeLink(self.as_ref().map(|nd| nd.clone()))
    }
}
impl<T: Display + Ord + PartialOrd> EdgeLink<T> {
    fn new() -> Self {
        EdgeLink(None)
    }
    fn from(weight: i32, from: T, to: T) -> Self {
        EdgeLink(Some(Rc::new(RefCell::new(Edge::new(weight, from, to)))))
    }
    fn inner(&self) -> Ref<Edge<T>> {
        self.as_ref().unwrap().borrow()
    }
}

struct SetLink<T: Display + Ord>(Rc<RefCell<HashSet<NodeLink<T>>>>);
impl<T: Display + Ord> SetLink<T> {
    fn new(node: NodeLink<T>) -> Self {
        let set = Rc::new(RefCell::new(HashSet::new()));
        set.borrow_mut().insert(node);
        SetLink(set)
    }
}
impl<T: Display + Ord> Deref for SetLink<T> {
    type Target = Rc<RefCell<HashSet<NodeLink<T>>>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T: Display + Ord> Clone for SetLink<T> {
    fn clone(&self) -> Self {
        SetLink(self.0.clone())
    }
}

struct UnionFindSet<T: Display + Ord>(HashMap<NodeLink<T>, SetLink<T>>);
impl<T: Display + Ord> Deref for UnionFindSet<T> {
    type Target = HashMap<NodeLink<T>, SetLink<T>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T: Display + Ord> DerefMut for UnionFindSet<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}
impl<T: Display + Ord> UnionFindSet<T> {
    fn from(nodes: &[NodeLink<T>]) -> Self {
        let mut map: HashMap<NodeLink<T>, SetLink<T>> = HashMap::new();
        for node in nodes {
            map.insert(node.clone(), SetLink::new(node.clone()));
        }
        UnionFindSet(map)
    }

    fn is_same(&self, from: &NodeLink<T>, to: &NodeLink<T>) -> bool {
        if self.get(from).is_none() || self.get(to).is_none() {
            return false;
        }

        self.get(from).unwrap().borrow().contains(to)
            || self.get(to).unwrap().borrow().contains(from)
    }

    fn union(&mut self, from: &NodeLink<T>, to: &NodeLink<T>) {
        let from_set = self.get(from).unwrap();
        let to_set = self.get(to).unwrap();

        for node in to_set.borrow_mut().drain() {
            from_set.borrow_mut().insert(node);
        }

        let fset = from_set.clone();
        self.get_mut(to).map(|set| *set = fset);
    }
}

struct Graph<T: Display + Ord + PartialOrd> {
    nodes: HashMap<T, NodeLink<T>>,
    edges: Vec<EdgeLink<T>>,
}
impl<T: Display + Hash + Eq + Copy + Ord + PartialOrd> Graph<T> {
    fn new() -> Self {
        Self {
            nodes: HashMap::new(),
            edges: Vec::new(),
        }
    }

    fn from(&mut self, array: &[(i32, T, T)]) -> &mut Self {
        let mut from: T;
        let mut to: T;
        let mut weight: i32;
        let mut edge: EdgeLink<T>;

        for info in array {
            weight = info.0;
            from = info.1;
            to = info.2;

            edge = EdgeLink::from(weight, from, to);
            self.nodes.entry(from).or_insert(NodeLink::new(from));
            self.nodes.entry(to).or_insert(NodeLink::new(to));
            self.edges.push(edge.clone());

            let to_node = self.nodes.get(&to).unwrap();

            self.nodes.get(&from).map(|n| {
                n.inner_mut().out_dgree += 1;
                n.inner_mut().next.push(to_node.clone());
                n.inner_mut().edges.push(edge);
            });
            to_node.inner_mut().in_dgree += 1;
        }
        self
    }

    fn bfs(&self, start: &NodeLink<T>) {
        let mut queue: VecDeque<NodeLink<T>> = VecDeque::new();
        let mut set: HashSet<NodeLink<T>> = HashSet::new();
        let root = start.clone();
        queue.push_front(root);

        while let Some(node) = queue.pop_back() {
            if set.contains(&node) {
                continue;
            }
            print!("{}, ", node.inner().no);
            set.insert(node.clone());

            for next in &node.inner().next {
                if !set.contains(next) {
                    queue.push_front(next.clone());
                }
            }
        }
        println!();
    }

    fn dfs(&self, start: &NodeLink<T>) {
        let mut stack: Vec<NodeLink<T>> = Vec::new();
        let mut set: HashSet<NodeLink<T>> = HashSet::new();
        let root = start.clone();
        print!("{}, ", root.inner().no);
        set.insert(root.clone());
        stack.push(root);

        while let Some(node) = stack.pop() {
            for next in &node.inner().next {
                if !set.contains(&next) {
                    stack.push(node.clone());
                    stack.push(next.clone());
                    print!("{}, ", next.inner().no);
                    set.insert(next.clone());
                    break;
                }
            }
        }
        println!();
    }

    fn find_zero_indegree(&self) -> NodeLink<T> {
        for node in self.nodes.values() {
            if node.inner().in_dgree == 0 {
                return node.clone();
            }
        }
        NodeLink(None)
    }

    fn sorted_topology(&self) {
        if self.find_zero_indegree().is_none() {
            println!("没有入度为0的节点");
            return;
        }

        print!("拓扑序列：[");
        let mut zero_in: Vec<NodeLink<T>> = Vec::new();
        zero_in.push(self.find_zero_indegree());

        while let Some(node) = zero_in.pop() {
            print!("{} -> ", node.inner().no);
            for next in &node.inner().next {
                next.as_ref().map(|node| {
                    node.borrow_mut().in_dgree -= 1;
                    if node.borrow().in_dgree == 0 {
                        zero_in.push(next.clone());
                    }
                });
            }
        }

        println!("END]");
    }

    fn kruskal_mst(&self) {
        println!("\n克鲁斯卡尔最小生成树：");
        let mut min_heap = BinaryHeap::new();
        let mut set = HashSet::new();
        let mut nodes: Vec<NodeLink<T>> = vec![];

        for edge in &self.edges {
            min_heap.push(Reverse(edge.clone()));
            set.insert(edge.inner().from.clone());
            set.insert(edge.inner().to.clone());
        }
        for n in set {
            nodes.push(self.nodes.get(&n).unwrap().clone());
        }
        let mut ufset = UnionFindSet::from(&nodes[..]);

        let mut from;
        let mut to;
        while let Some(Reverse(edge)) = min_heap.pop() {
            from = self.nodes.get(&edge.inner().from).unwrap().clone();
            to = self.nodes.get(&edge.inner().to).unwrap().clone();
            if !ufset.is_same(&from, &to) {
                println!("{}", edge);
                ufset.union(&from, &to);
            }
        }
    }

    fn prime_mst(g: &Graph<T>) {
        let mut min_heap: BinaryHeap<Reverse<EdgeLink<T>>> = BinaryHeap::new();
        let mut node_set: HashSet<NodeLink<T>> = HashSet::new();
        let mut edge_set: HashSet<EdgeLink<T>> = HashSet::new();
        let start = g.nodes.values().next().unwrap().clone();
        for edge in &start.inner().edges {
            min_heap.push(Reverse(edge.clone()));
            edge_set.insert(edge.clone());
        }
        node_set.insert(start.clone());
        println!("prime最小生成树： ");

        while let Some(Reverse(edge)) = min_heap.pop() {
            let from = g.nodes.get(&edge.inner().from).unwrap();
            let to = g.nodes.get(&edge.inner().to).unwrap();

            if node_set.contains(from) && node_set.contains(to) {
                continue;
            }
            println!("{}, ", edge);

            let node = if !node_set.contains(from) { from } else { to };
            node_set.insert(node.clone());
            for e in &node.inner().edges {
                if !edge_set.contains(e) {
                    min_heap.push(Reverse(e.clone()));
                }
            }
        }
        println!("END]");
    }

    fn find_node(g: &Graph<T>, no: T) -> NodeLink<T> {
        g.nodes.get(&no).unwrap().clone()
    }

    fn find_mindist(
        node_dist: &HashMap<NodeLink<T>, u32>,
        set: &HashSet<NodeLink<T>>,
    ) -> NodeLink<T> {
        let mut minval: u32 = u32::MAX;
        let mut node: NodeLink<T> = NodeLink(None);
        for (k, v) in node_dist {
            if set.contains(k) {
                continue;
            }

            if minval > *v {
                minval = *v;
                node = k.clone();
            }
        }
        node
    }

    fn dijkstra(g: &Graph<T>, start: &NodeLink<T>) {
        let mut node_dist: HashMap<NodeLink<T>, u32> = HashMap::new();
        let mut set: HashSet<NodeLink<T>> = HashSet::new();

        for node in g.nodes.values() {
            node_dist.insert(node.clone(), u32::MAX);
        }
        node_dist.insert(start.clone(), 0);
        let mut node = start.clone();

        while node.is_some() {
            for edge in &node.inner().edges {
                let to = Graph::find_node(g, edge.inner().to);
                let from = Graph::find_node(g, edge.inner().from);
                let origin_dist = *node_dist.get(&to).unwrap();
                let new_dist = *node_dist.get(&from).unwrap() + edge.inner().weight as u32;
                if origin_dist > new_dist {
                    *node_dist.get_mut(&to).unwrap() = new_dist;
                }
            }
            set.insert(node.clone());

            node = Graph::find_mindist(&node_dist, &set);
        }

        print!("Djkstra [A] 到其他节点的最短路径：");
        for (k, v) in &node_dist {
            print!("({}: {}) ", k.inner().no, v);
        }
        println!()
    }
}

struct DistNode<T: Display + Ord>(HashMap<u32, NodeLink<T>>);
impl<T: Display + Ord> Deref for DistNode<T> {
    type Target = HashMap<u32, NodeLink<T>>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

fn print_graph<T: Display + Ord>(g: &Graph<T>) {
    println!("========== nodes ==========");
    for v in g.nodes.values() {
        println!("{}", v);
    }
    println!("========== edges ==========");
    for v in &g.edges {
        println!("edge: {}", v);
    }
}

pub fn graph_main() {
    let matrix = [
        (5, 11, 12),
        (6, 11, 21),
        (7, 12, 13),
        (1, 12, 22),
        (1, 13, 14),
        (1, 13, 23),
        (1, 14, 24),
        (1, 21, 22),
        (1, 21, 31),
        (1, 22, 23),
        (1, 22, 32),
        (1, 23, 24),
        (1, 23, 33),
        (1, 24, 34),
        (1, 31, 32),
        (1, 31, 41),
        (1, 32, 33),
        (1, 32, 42),
        (1, 33, 34),
        (1, 33, 43),
        (1, 34, 44),
        (1, 41, 42),
        (1, 42, 43),
        (1, 43, 44),
    ];

    let mut graph = Graph::new();
    graph.from(&matrix);
    print_graph(&graph);

    let matrix: [(i32, char, char); 8] = [
        (1, 'A', 'B'),
        (2, 'A', 'C'),
        (3, 'A', 'D'),
        (4, 'B', 'C'),
        (5, 'C', 'D'),
        (6, 'C', 'E'),
        (7, 'B', 'E'),
        (8, 'D', 'E'),
    ];
    let mut graph = Graph::new();
    graph.from(&matrix);
    print_graph(&graph);

    println!("\n广度优先遍历：");
    graph.bfs(graph.nodes.get(&'A').unwrap());

    println!("\n深度优先遍历：");
    graph.dfs(graph.nodes.get(&'A').unwrap());
    graph.sorted_topology();

    let mut nodes: Vec<NodeLink<char>> = vec![];
    for n in graph.nodes.values() {
        nodes.push(n.clone());
    }

    graph.kruskal_mst();

    let matrix: Vec<(i32, char, char)> = vec![
        (1, 'A', 'C'),
        (1, 'C', 'A'),
        (6, 'A', 'B'),
        (6, 'B', 'A'),
        (5, 'A', 'D'),
        (5, 'D', 'A'),
        (5, 'B', 'C'),
        (5, 'C', 'B'),
        (3, 'B', 'E'),
        (3, 'E', 'B'),
        (5, 'C', 'D'),
        (5, 'D', 'C'),
        (4, 'C', 'F'),
        (4, 'F', 'C'),
        (2, 'D', 'F'),
        (2, 'F', 'D'),
        (6, 'E', 'F'),
        (6, 'F', 'E'),
    ];
    let mut graph = Graph::new();
    graph.from(&matrix[..]);
    print_graph(&graph);
    Graph::prime_mst(&graph);

    println!("=========单元最短距离===========");
    let matrix: Vec<(i32, char, char)> = vec![
        (3, 'A', 'B'),
        (3, 'B', 'A'),
        (15, 'A', 'C'),
        (15, 'C', 'A'),
        (9, 'A', 'D'),
        (9, 'D', 'A'),
        (2, 'B', 'C'),
        (2, 'C', 'B'),
        (200, 'B', 'E'),
        (200, 'E', 'B'),
        (7, 'C', 'D'),
        (7, 'D', 'C'),
        (14, 'C', 'E'),
        (14, 'E', 'C'),
        (16, 'D', 'E'),
        (16, 'E', 'D'),
    ];
    let mut graph = Graph::new();
    graph.from(&matrix[..]);
    print_graph(&graph);
    let start = graph.nodes.get(&'A').unwrap();
    Graph::dijkstra(&graph, start);
}
